package com.cat.DataStructure04;

import java.util.*;

/**
*   @description https://leetcode.cn/problems/visit-array-positions-to-maximize-score/
*   @author 曲大人的喵
*   @create 2025/11/30 17:48
*   @since JDK17
*/

public class Solution29 {
    long[][] dp;
    int x;
    long f(int[] nums, int i, int cur) {
        if (i == nums.length) {
            return 0;
        }
        if (dp[i][cur] != -1) {
            return dp[i][cur];
        }
        if (cur != nums[i] % 2) {
            return dp[i][cur] = f(nums, i + 1, cur);
        }
        long p1 = f(nums, i + 1, cur);
        long p2 = f(nums, i + 1, cur ^ 1) - x;
        return dp[i][cur] = Math.max(p1, p2) + nums[i];
    }
    public long maxScore(int[] nums, int x) {
        int n = nums.length;
        dp = new long[n][2];
        this.x = x;
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }

        return f(nums, 0, nums[0] % 2);
    }
}
